Претрага у дубину

Претрага у дубину можемо описати на следећи начин. Замислимо да обилазимо музеј који се састоји од повезаних сала. Музеј обилазимо тако што из сваке сале у коју дођемо прелазимо у неку наредну, до тада непосећену салу, све док је то могуће. Тек када то није могуће, враћамо се у салу из које смо дошли у текућу и проверавамо да ли из ње можемо одемо у неку до тада не посећену салу. Обилазак се завршава када се вратимо у почетну салу и установимо да из ње више не можемо да одемо ни у једну салу у којој до тада нисмо били.

Постоје два уобичајена начина да се имплементира претрага у дубину:

• рекурзивна имплементација

• имплементација уз помоћ стека

Прикажимо обе имплементације у облику псеудокода.

Рекурзивна имплементација:

obidji(polje):
   obelezi polje
   za sve neobelezene susede polja:
      obidji(sused)

Имплементација уз помоћ стека:

obidji(pocetno_polje):
   stavi pocetno_polje na stek
   obelezi pocetno_polje
   dok stek nije prazan:
      skini polje sa vrha steka
      za neobelezene susede tog polja:
         stavi suseda na stek
         obelezi suseda